package com.Offer;

/*
    面试题12：矩阵中的路劲
    题目描述：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串 所有字符的路径。
    路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向 左，向右，向上，向下移动一个格子。
    如果一条路径经过了矩阵中的某一个格子， 则该路径不能再进入该格子。
 */
public class demo12 {

    public static void main(String[] args) {

    }

    public static   boolean hasPath(char[] matrix,int rows,int cols,char[] str){
        int flag[] = new int[matrix.length];
        for(int i = 0;i<rows;i++){
            for(int j = 0;j<cols;j++){
                if(helper(matrix,rows,cols,i,j,str,0,flag))
                    return true;
            }
        }
        return false;
    }

    public static boolean helper(char[] matrix,int rows,int cols,int i,int j,char[] str,int k,int[] flag){
        int index = i*cols+j;
        if(i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1){
            return false;
        }

        if(k == str.length-1)return true;
        flag[index] = 1;

        if(helper(matrix,rows,cols,i-1,j,str,k+1,flag)
                || helper(matrix,rows,cols,i+1,j,str,k+1,flag)
                || helper(matrix,rows,cols,i,j-1,str,k+1,flag)
                || helper(matrix,rows,cols,i,j+1,str,k+1,flag))
            return true;
        flag[index] = 0;
        return false;
    }
}
